Cancelling in Linear Congruences

This note deals with two circumstances in which terms may be divided through in linear congruences without effecting the set of solutions.

Proof

$x$ is a solution to the congruence $ax=b(\mathrm{mod}m)$ if and only if there exists a $y$ such that:

It is easy to then see that multiplying through by $c\ne 0$ has no effect on the solution set.

Proof

We will show this be showing two implications. First, if $x$ is a solution to the equation $ax=b(\mathrm{mod}m)$, it is necessarily a solution to $cax=cb(\mathrm{mod}m)$.

In the opposite direction, we consider the following equivalent conditions:

This result can also be proven by using the existence of an inverse for $c$ given the coprimality condition.